package org.nowcoder.huawei.c200;

/**
 * 25 : 模拟目录管理功能
 */
public class HC025 {

    public static void main(String[] args) {
        dijkstra(new int[][]{{0, 2, 4}, {2, 0, 1}, {4, 1, 0}}, 0);
    }

    //单源最短路径问题
    public static void dijkstra(int[][] graph, int start) {
        boolean[] visited = new boolean[graph.length];
        visited[start] = true;
        int[] distance = new int[graph.length];

        for (int i = 0; i < graph.length; i++) {
            distance[i] = graph[start][i];
        }

        for (int i = 1; i < graph.length; i++) {
            //找到start距离最短的i
            int min = Integer.MAX_VALUE;
            int index = 0;
            for (int j = 0; j < graph.length; j++) {
                if (!visited[j] && j != start && distance[j] < min) {
                    min = distance[j];
                    index = j;
                }
            }

            visited[index] = true;
            for (int j = 0; j < graph.length; j++) {
                if (!visited[j] && j != index && distance[index] + graph[index][j] < distance[j]) {
                    distance[j] = distance[index] + graph[index][j];
                }
            }
        }
    }
}

